package mapandset;

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null) {
            root = node;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.key == key) {
                return false;
            } else if(cur.key > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }

        if(key < prev.key) {
            prev.left = node;
        } else {
            prev.right = node;
        }

        return true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.key == key) {
                return cur;
            } else if(cur.key > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }

    //删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.key == key) {
                removeNode(prev,cur);
                return true;
            } else if(cur.key > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }
        return false;
    }

    private void removeNode(TreeNode parent, TreeNode del) {
        if(del.left == null) {
            if(del == root) {
                root = del.right;
            } else if(parent.left == del) {
                parent.left = del.right;
            } else {
                parent.right = del.right;
            }
        }else if(del.right == null) {
            if(del == root) {
                root = del.left;
            } else if(parent.left == del) {
                parent.left = del.left;
            } else {
                parent.right = del.left;
            }
        } else {
            TreeNode cur = del.left;
            TreeNode prev = del;
            while(cur.right != null) {
                prev = cur;
                cur = cur.right;
            }
            del.key = cur.key;
            if(prev.left == cur) {
                prev.left = cur.left;
            } else {
                prev.right = cur.left;
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(9);
        bst.insert(3);
        bst.insert(18);

        BinarySearchTree.TreeNode ret = bst.search(15);
        System.out.println(ret.key);

        bst.remove(10);

    }
}